package 力扣._00周赛._144双周赛.问题3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution2 {
    public int maxRemoval(int[] nums, int[][] queries) {
        // 差分数组
        int[] diff = new int[nums.length + 1];
        for (int[] query : queries) {
            diff[query[0]]++;
            diff[query[1] + 1]--;
        }
        // 对应真实数组
        int[] real = new int[nums.length];
        real[0] = diff[0];
        for (int i = 1; i < nums.length; i++) {
            real[i] = real[i - 1] + diff[i];
        }
        // 得到多余值
        for (int i = 0; i < nums.length; i++) {
            real[i] = real[i] - nums[i];
            if(real[i] < 0) {
                return -1;
            }
        }
        // 尽可能多的删除queries但要保证real数组中的值都 >= 0
        int res = 0;
        // 背包？ 视query为物品，real为背包容量, 每个query的价值为1
        // dp[i][j]表示前i个query，背包容量为j时的最大价值
        int[][] dp = new int[queries.length + 1][nums.length + 1];
        for (int i = 1; i <= queries.length; i++) {
            int left = queries[i - 1][0], right = queries[i - 1][1];
            for (int j = 1; j <= nums.length; j++) {
                dp[i][j] = dp[i - 1][j];
                boolean flag = true;
                for (int k = left; k <= right; k++) {
                    if (real[k] <= 0) {
                        flag = false;
                        break;
                    }
                }
                if(flag) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - (right - left + 1)] + 1);
                    for (int k = left; k <= right; k++) {
                        real[k]--;
                    }
                }
            }
        }
        return res;

    }
}